<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            LeetCode贪心 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">LeetCode贪心</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2020-01-21 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/LeetCode/">LeetCode</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E8%B4%AA%E5%BF%83/">贪心</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>11.3k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>51 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="455-分发饼干"><a href="#455-分发饼干" class="headerlink" title="455. 分发饼干"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/assign-cookies/" >455. 分发饼干<i class="fas fa-external-link-alt"></i></a></h2><p>假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj &gt;= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。</p>
<p><strong>注意：</strong></p>
<p>你可以假设胃口值为正。<br>一个小朋友最多只能拥有一块饼干</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>], [<span class="number">1</span>,<span class="number">1</span>]</span><br><span class="line"></span><br><span class="line">输出: <span class="number">1</span></span><br><span class="line"></span><br><span class="line">解释: </span><br><span class="line">你有三个孩子和两块小饼干，<span class="number">3</span>个孩子的胃口值分别是：<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>。</span><br><span class="line">虽然你有两块小饼干，由于他们的尺寸都是<span class="number">1</span>，你只能让胃口值是<span class="number">1</span>的孩子满足。</span><br><span class="line">所以你应该输出<span class="number">1</span>。</span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">2</span>], [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>]</span><br><span class="line"></span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line"></span><br><span class="line">解释: </span><br><span class="line">你有两个孩子和三块小饼干，<span class="number">2</span>个孩子的胃口值分别是<span class="number">1</span>,<span class="number">2</span>。</span><br><span class="line">你拥有的饼干数量和尺寸都足以让所有孩子满足。</span><br><span class="line">所以你应该输出<span class="number">2.</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>贪就完事儿了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findContentChildren</span><span class="params">(<span class="keyword">int</span>[] g, <span class="keyword">int</span>[] s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (g==<span class="keyword">null</span> || s==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Arrays.sort(g);</span><br><span class="line">    Arrays.sort(s);</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>,index=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;g.length;i++) &#123;</span><br><span class="line">        <span class="keyword">while</span>(index&lt;s.length)&#123;</span><br><span class="line">            <span class="keyword">if</span> (g[i]&lt;=s[index]) &#123;</span><br><span class="line">                res++;</span><br><span class="line">                index++;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            index++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="274-H指数"><a href="#274-H指数" class="headerlink" title="274. H指数"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/h-index/" >274. H指数<i class="fas fa-external-link-alt"></i></a></h2><p>给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。</p>
<p>h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）<del>至多</del>有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: citations = [<span class="number">3</span>,<span class="number">0</span>,<span class="number">6</span>,<span class="number">1</span>,<span class="number">5</span>]</span><br><span class="line">输出: <span class="number">3</span> </span><br><span class="line">解释: 给定数组表示研究者总共有 <span class="number">5</span> 篇论文，每篇论文相应的被引用了 <span class="number">3</span>, <span class="number">0</span>, <span class="number">6</span>, <span class="number">1</span>, <span class="number">5</span> 次。</span><br><span class="line">     由于研究者有 <span class="number">3</span> 篇论文每篇至少被引用了 <span class="number">3</span> 次，其余两篇论文每篇被引用不多于 <span class="number">3</span> 次，所以她的 h 指数是 <span class="number">3</span>。</span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong> 如果 h 有多种可能的值，h 指数是其中最大的那个。</p>
<p><strong>解法一</strong></p>
<p>题目意思搞懂就ok</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">hIndex</span><span class="params">(<span class="keyword">int</span>[] citations)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> len=citations.length;</span><br><span class="line">    Arrays.sort(citations);</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=len-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--) &#123;</span><br><span class="line">        <span class="keyword">if</span> (citations[i]&lt;=len-(i+<span class="number">1</span>)) &#123;</span><br><span class="line">            <span class="keyword">return</span> len-(i+<span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> len;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="392-判断子序列"><a href="#392-判断子序列" class="headerlink" title="392. 判断子序列"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/is-subsequence/" >392. 判断子序列<i class="fas fa-external-link-alt"></i></a></h2><p>给定字符串 s 和 t ，判断 s 是否为 t 的子序列。</p>
<p>你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 &lt;=100）。</p>
<p>字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，<code>&quot;ace&quot;</code>是<code>&quot;abcde&quot;</code>的一个子序列，而<code>&quot;aec&quot;</code>不是）。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">s = <span class="string">&quot;abc&quot;</span>, t = <span class="string">&quot;ahbgdc&quot;</span></span><br><span class="line">返回 <span class="keyword">true</span>.</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">s = <span class="string">&quot;axc&quot;</span>, t = <span class="string">&quot;ahbgdc&quot;</span></span><br><span class="line">返回 <span class="keyword">false</span>.</span><br></pre></td></tr></table></figure>

<p><strong>后续挑战 :</strong></p>
<p>如果有大量输入的 S，称作S1, S2, … , Sk 其中 k &gt;= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isSubsequence</span><span class="params">(String s, String t)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s==<span class="keyword">null</span> || t==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> sindex=<span class="number">0</span>,tindex=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(sindex&lt;s.length()) &#123;</span><br><span class="line">        <span class="keyword">while</span>(tindex&lt;t.length() &amp;&amp; sindex&lt;s.length())&#123;</span><br><span class="line">            <span class="keyword">if</span> (s.charAt(sindex)==t.charAt(tindex)) &#123;</span><br><span class="line">                sindex++;</span><br><span class="line">            &#125;</span><br><span class="line">            tindex++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (tindex==t.length()) &#123;</span><br><span class="line">            <span class="keyword">break</span>; </span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sindex==s.length();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以改成递归（多练习递归）</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isSubsequence</span><span class="params">(String s,String t)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> subsequence(s,t,<span class="number">0</span>,<span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">subsequence</span><span class="params">(String s,String t,<span class="keyword">int</span> sindex,<span class="keyword">int</span> tindex)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (sindex == s.length()) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//上下if不能交换,可能最后一个才相等</span></span><br><span class="line">    <span class="keyword">if</span> (tindex == t.length()) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> s.charAt(sindex)==t.charAt(tindex)?subsequence(s,t,sindex+<span class="number">1</span>,tindex+<span class="number">1</span>):subsequence(s,t,sindex,tindex+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//大量的s字符串 处理</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isSubsequence3</span><span class="params">(String s, String t)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//预处理</span></span><br><span class="line">    ArrayList&lt;ArrayList&lt;Integer&gt;&gt; hash=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">26</span>;i++) &#123;</span><br><span class="line">        hash.add(<span class="keyword">new</span> ArrayList());</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;t.length();i++) &#123;</span><br><span class="line">        hash.get(t.charAt(i)-<span class="string">&#x27;a&#x27;</span>).add(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//经过上面的预处理,后面的处理就会很快,不用再遍历t字符串</span></span><br><span class="line">    <span class="keyword">int</span> lastIndex=-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        List&lt;Integer&gt; indexList=hash.get(s.charAt(i)-<span class="string">&#x27;a&#x27;</span>);</span><br><span class="line">        <span class="keyword">int</span> temp=binarySearch(indexList,lastIndex);</span><br><span class="line">        <span class="keyword">if</span> (temp==indexList.size()) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        lastIndex=indexList.get(temp);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//找到第一个比target大的元素</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(List&lt;Integer&gt; list,<span class="keyword">int</span> target)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>,right=list.size()-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(left&lt;=right)&#123;</span><br><span class="line">        <span class="keyword">int</span> mid=left+(right-left)/<span class="number">2</span>;</span><br><span class="line">        <span class="keyword">if</span> (list.get(mid)&gt;target) &#123;</span><br><span class="line">            right=mid-<span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            left=mid+<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> left;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="621-任务调度器"><a href="#621-任务调度器" class="headerlink" title="621. 任务调度器"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/task-scheduler/" >621. 任务调度器<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。</p>
<p>然而，两个<strong>相同种类</strong>的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。</p>
<p>你需要计算完成所有任务所需要的<strong>最短时间</strong></p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: tasks = [<span class="string">&quot;A&quot;</span>,<span class="string">&quot;A&quot;</span>,<span class="string">&quot;A&quot;</span>,<span class="string">&quot;B&quot;</span>,<span class="string">&quot;B&quot;</span>,<span class="string">&quot;B&quot;</span>], n = <span class="number">2</span></span><br><span class="line">输出: <span class="number">8</span></span><br><span class="line">执行顺序: A -&gt; B -&gt; (待命) -&gt; A -&gt; B -&gt; (待命) -&gt; A -&gt; B.</span><br></pre></td></tr></table></figure>

<p><strong>注：</strong></p>
<ul>
<li>任务的总个数为 <code>[1, 10000]</code></li>
<li>n 的取值范围为 <code>[0, 100]</code></li>
</ul>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">leastInterval</span><span class="params">(<span class="keyword">char</span>[] tasks, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] map=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">26</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;tasks.length;i++) &#123;</span><br><span class="line">        map[tasks[i]-<span class="string">&#x27;A&#x27;</span>]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//找最大值</span></span><br><span class="line">    <span class="keyword">int</span> max=-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;map.length;i++) &#123;</span><br><span class="line">        max=Math.max(map[i],max);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> maxCount=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;map.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (map[i]==max) &#123;</span><br><span class="line">            maxCount++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//比如 a b c d e f g,n=1</span></span><br><span class="line">    <span class="keyword">return</span> Math.max((n+<span class="number">1</span>)*(max-<span class="number">1</span>)+maxCount,tasks.length);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>核心思想就是将出现次数最多的任务优先执行并且尽可能的分散，比如  <code>A A A B B C n=2</code> 最短的时间就是<code>A X X A X X A</code> ，最终的时间就是<code>(n+1)*(max-1)+1</code> 也就是 <code>(2+1) *(3-1)+1=7</code>， 但是可能会有多个最多次数的任务，所以我们还需要加上最多的相同的个数，最后就是 <code>(n+1)*(max-1)+maxCount</code> ，但是还不够，还是有可能会出现代码中的例子，也就是最后得到的结果比我们的任务列表还有短，所以我们需要取一个最大值</p>
<h2 id="55-跳跃游戏"><a href="#55-跳跃游戏" class="headerlink" title="55. 跳跃游戏"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/jump-game/" >55. 跳跃游戏<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个非负整数数组，你最初位于数组的第一个位置。</p>
<p>数组中的每个元素代表你在该位置可以跳跃的最大长度。</p>
<p>判断你是否能够到达最后一个位置。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">2</span>,<span class="number">3</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">4</span>]</span><br><span class="line">输出: <span class="keyword">true</span></span><br><span class="line">解释: 我们可以先跳 <span class="number">1</span> 步，从位置 <span class="number">0</span> 到达 位置 <span class="number">1</span>, 然后再从位置 <span class="number">1</span> 跳 <span class="number">3</span> 步到达最后一个位置。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">4</span>]</span><br><span class="line">输出: <span class="keyword">false</span></span><br><span class="line">解释: 无论怎样，你总会到达索引为 <span class="number">3</span> 的位置。但该位置的最大跳跃长度是 <span class="number">0</span> ， 所以你永远不可能到达最后一个位置。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>回溯，勉强能过。。。太蠢了，为啥想不到简单的方法，就非得往复杂了想？就这么傻么？</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Boolean[] cache=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canJump</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    cache=<span class="keyword">new</span> Boolean[nums.length];</span><br><span class="line">    <span class="keyword">return</span> jump(nums,<span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">jump</span><span class="params">(<span class="keyword">int</span>[] nums,<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums[index] &gt;= nums.length-<span class="number">1</span> -index) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (cache[index]!=<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[index];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=nums[index];i&gt;=<span class="number">1</span>;i--) &#123;</span><br><span class="line">        <span class="keyword">if</span> (index+i&lt;nums.length &amp;&amp; jump(nums,index+i)) &#123;</span><br><span class="line">            <span class="keyword">return</span> cache[index]=<span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> cache[index]=<span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>不用多说了，遍历数组，不断更新能到达的最远距离，如果<strong>某个位置的index大于当前能到达的最远距离就直接返回false</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//MDZZ</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canJump</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> maxIndex=nums[<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length-<span class="number">1</span>;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(maxIndex &gt;= nums.length-<span class="number">1</span>) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">if</span> (i&gt;maxIndex) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        maxIndex=Math.max(maxIndex,i+nums[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="45-跳跃游戏-II"><a href="#45-跳跃游戏-II" class="headerlink" title="45. 跳跃游戏 II"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/jump-game-ii/" >45. 跳跃游戏 II<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个非负整数数组，你最初位于数组的第一个位置。</p>
<p>数组中的每个元素代表你在该位置可以跳跃的最大长度。</p>
<p>你的目标是使用最少的跳跃次数到达数组的最后一个位置。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">2</span>,<span class="number">3</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">4</span>]</span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line">解释: 跳到最后一个位置的最小跳跃数是 <span class="number">2</span>。</span><br><span class="line">     从下标为 <span class="number">0</span> 跳到下标为 <span class="number">1</span> 的位置，跳 <span class="number">1</span> 步，然后跳 <span class="number">3</span> 步到达数组的最后一个位置。</span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<p>假设你总是可以到达数组的最后一个位置。</p>
<p><strong>解法一</strong></p>
<p>兴致勃勃写了个dp</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">jump</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[nums.length];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        dp[i]=Integer.MAX_VALUE;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;i;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[j]&gt;=i-j) &#123;</span><br><span class="line">                dp[i]=Math.min(dp[j]+<span class="number">1</span>,dp[i]);    </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[nums.length-<span class="number">1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>如果这就过了那你也太小瞧这题了😂人家可是hard题，那能这么容易就让你过了？</p>
<p>没错，这里直接TLE了，最后一个CASE过不去</p>
<p><strong>解法二</strong></p>
<p>贪心，核心思想不是每次都跳到最远的地方，<strong>而是跳到当前位置能跳到的最远的位置</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//每次选能跳的位置中跳的最远的</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">jump</span><span class="params">(<span class="keyword">int</span>[] nums)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> max=<span class="number">0</span>;<span class="comment">//最大边界</span></span><br><span class="line">    <span class="keyword">int</span> step=<span class="number">0</span>,curMaxIndex=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length-<span class="number">1</span>;i++) &#123;</span><br><span class="line">        curMaxIndex=Math.max(curMaxIndex,nums[i]+i); <span class="comment">//i能跳的位置中,跳的最远的</span></span><br><span class="line">        <span class="keyword">if</span> (i==max) &#123;<span class="comment">//走到边界就++</span></span><br><span class="line">            step++;</span><br><span class="line">            max=curMaxIndex;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> step;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>代码需要细细品，一下可能看不太明白</p>
<p><strong>解法三</strong></p>
<p>回顾的时候这道题始终是没搞清楚，<a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/jump-game-ii/solution/xun-huan-bu-bian-shi-fen-xi-cban-by-huai-an-2/" >看了一个大佬的题解<i class="fas fa-external-link-alt"></i></a> （这个大佬好像是个初中的妹子）后明白了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//参考了一个大佬循环不变表达式的分析</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">jump</span><span class="params">(<span class="keyword">int</span>[] nums)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//当前这一跳能选择的最远距离</span></span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//目前能达到的最远距离</span></span><br><span class="line">    <span class="keyword">int</span> right=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> ptr=<span class="number">0</span>,step=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (right&lt;nums.length-<span class="number">1</span>) &#123;</span><br><span class="line">        left=right;</span><br><span class="line">        <span class="keyword">while</span>(ptr&lt;nums.length &amp;&amp; ptr&lt;=left) &#123;</span><br><span class="line">            right=Math.max(right,nums[ptr]+ptr);</span><br><span class="line">            ptr++;</span><br><span class="line">        &#125;</span><br><span class="line">        step++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> step;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="56-合并区间"><a href="#56-合并区间" class="headerlink" title="56. 合并区间"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/merge-intervals/" >56. 合并区间<i class="fas fa-external-link-alt"></i></a></h2><p>给出一个区间的集合，请合并所有重叠的区间。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [[<span class="number">1</span>,<span class="number">3</span>],[<span class="number">2</span>,<span class="number">6</span>],[<span class="number">8</span>,<span class="number">10</span>],[<span class="number">15</span>,<span class="number">18</span>]]</span><br><span class="line">输出: [[<span class="number">1</span>,<span class="number">6</span>],[<span class="number">8</span>,<span class="number">10</span>],[<span class="number">15</span>,<span class="number">18</span>]]</span><br><span class="line">解释: 区间 [<span class="number">1</span>,<span class="number">3</span>] 和 [<span class="number">2</span>,<span class="number">6</span>] 重叠, 将它们合并为 [<span class="number">1</span>,<span class="number">6</span>].</span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [[<span class="number">1</span>,<span class="number">4</span>],[<span class="number">4</span>,<span class="number">5</span>]]</span><br><span class="line">输出: [[<span class="number">1</span>,<span class="number">5</span>]]</span><br><span class="line">解释: 区间 [<span class="number">1</span>,<span class="number">4</span>] 和 [<span class="number">4</span>,<span class="number">5</span>] 可被视为重叠区间。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>思路也没啥好说的，类似贪心吧</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[][] merge(<span class="keyword">int</span>[][] intervals) &#123;</span><br><span class="line">    <span class="keyword">if</span> (intervals ==<span class="keyword">null</span> || intervals.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[][]&#123;&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    Arrays.sort(intervals,(a,b)-&gt;a[<span class="number">0</span>]-b[<span class="number">0</span>]);</span><br><span class="line">    LinkedList&lt;<span class="keyword">int</span>[]&gt; list=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;intervals.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (intervals[i][<span class="number">0</span>]&lt;=intervals[i-<span class="number">1</span>][<span class="number">1</span>]) &#123;</span><br><span class="line">            <span class="keyword">if</span> (intervals[i][<span class="number">1</span>]&gt;intervals[i-<span class="number">1</span>][<span class="number">1</span>]) &#123;</span><br><span class="line">                intervals[i][<span class="number">0</span>]=intervals[i-<span class="number">1</span>][<span class="number">0</span>];   </span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                intervals[i][<span class="number">0</span>]=intervals[i-<span class="number">1</span>][<span class="number">0</span>];</span><br><span class="line">                intervals[i][<span class="number">1</span>]=intervals[i-<span class="number">1</span>][<span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            list.add(intervals[i-<span class="number">1</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    list.add(intervals[intervals.length-<span class="number">1</span>]);</span><br><span class="line">    <span class="comment">/*  int[][] res=new int[list.size()][2];</span></span><br><span class="line"><span class="comment">        for (int i=0;i&lt;list.size();i++) &#123;</span></span><br><span class="line"><span class="comment">            res[i][0]=list.get(i)[0];</span></span><br><span class="line"><span class="comment">            res[i][1]=list.get(i)[1];</span></span><br><span class="line"><span class="comment">        &#125;*/</span></span><br><span class="line">    <span class="keyword">return</span> list.toArray(<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">0</span>][<span class="number">0</span>]); <span class="comment">//题解哪里学到一招</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>最大的收获就是学到了一招list转array的方法😁</p>
<p>偶然看到，简化下代码</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//update：2020.4.16</span></span><br><span class="line"><span class="comment">//偶然看到,简化下代码</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[][] merge(<span class="keyword">int</span>[][] intervals) &#123;</span><br><span class="line">    <span class="keyword">if</span> (intervals ==<span class="keyword">null</span> || intervals.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[][]&#123;&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    Arrays.sort(intervals,(a,b)-&gt;a[<span class="number">0</span>]-b[<span class="number">0</span>]);</span><br><span class="line">    LinkedList&lt;<span class="keyword">int</span>[]&gt; list=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;intervals.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (intervals[i][<span class="number">0</span>]&lt;=intervals[i-<span class="number">1</span>][<span class="number">1</span>]) &#123;</span><br><span class="line">            intervals[i][<span class="number">0</span>]=intervals[i-<span class="number">1</span>][<span class="number">0</span>];</span><br><span class="line">            intervals[i][<span class="number">1</span>]=Math.max(intervals[i-<span class="number">1</span>][<span class="number">1</span>],intervals[i][<span class="number">1</span>]);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            list.add(intervals[i-<span class="number">1</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    list.add(intervals[intervals.length-<span class="number">1</span>]);</span><br><span class="line">    <span class="keyword">return</span> list.toArray(<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">0</span>][<span class="number">0</span>]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>一开始还没注意这个解法，现在回头看看这个方法挺妙的，当无法覆盖的时候将<code>intervals[i-1]</code> 入栈，当可以覆盖的时候修改当前元素值，在下一轮继续添加或覆盖，其实还是有一点点不好理解，刚刚又重写了一个，思路很直白</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[][] merge(<span class="keyword">int</span>[][] intervals) &#123;</span><br><span class="line">    <span class="keyword">if</span>(intervals==<span class="keyword">null</span> || intervals.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> intervals;</span><br><span class="line">    Arrays.sort(intervals,(a,b)-&gt;a[<span class="number">0</span>]!=b[<span class="number">0</span>]?a[<span class="number">0</span>]-b[<span class="number">0</span>]:a[<span class="number">1</span>]-b[<span class="number">1</span>]);</span><br><span class="line">    List&lt;<span class="keyword">int</span>[]&gt; res=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    res.add(intervals[<span class="number">0</span>]);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;intervals.length;i++)&#123;</span><br><span class="line">        <span class="keyword">int</span>[] pre=res.get(res.size()-<span class="number">1</span>);</span><br><span class="line">        <span class="keyword">if</span>(intervals[i][<span class="number">0</span>]&lt;=pre[<span class="number">1</span>])&#123;</span><br><span class="line">            <span class="keyword">if</span>(intervals[i][<span class="number">1</span>]&gt;=pre[<span class="number">1</span>])&#123;</span><br><span class="line">                pre[<span class="number">1</span>]=intervals[i][<span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            res.add(intervals[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.toArray(<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">0</span>][<span class="number">0</span>]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="763-划分字母区间"><a href="#763-划分字母区间" class="headerlink" title="763. 划分字母区间"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/partition-labels/" >763. 划分字母区间<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>字符串 <code>S</code> 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入：S = <span class="string">&quot;ababcbacadefegdehijhklij&quot;</span></span><br><span class="line">输出：[<span class="number">9</span>,<span class="number">7</span>,<span class="number">8</span>]</span><br><span class="line">解释：</span><br><span class="line">划分结果为 <span class="string">&quot;ababcbaca&quot;</span>, <span class="string">&quot;defegde&quot;</span>, <span class="string">&quot;hijhklij&quot;</span>。</span><br><span class="line">每个字母最多出现在一个片段中。</span><br><span class="line">像 <span class="string">&quot;ababcbacadefegde&quot;</span>, <span class="string">&quot;hijhklij&quot;</span> 的划分是错误的，因为划分的片段数较少。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  <code>S</code>的长度在<code>[1, 500]</code>之间。</li>
<li>  <code>S</code>只包含小写字母 <code>&#39;a&#39;</code> 到 <code>&#39;z&#39;</code> 。</li>
</ul>
<p><strong>解法一</strong></p>
<p>我一开始的想法就是先统计出所有26个字母出现的首位置和末位置，然后题目就变成了<a href="#56-%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4">合并区间</a>，但是其实不需要真正的合并，这里只需要求长度就行了</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">partitionLabels</span><span class="params">(S <span class="keyword">string</span>)</span> []<span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> m = <span class="built_in">make</span>(<span class="keyword">map</span>[<span class="keyword">byte</span>]<span class="keyword">int</span>)</span><br><span class="line">    <span class="keyword">var</span> Max = <span class="function"><span class="keyword">func</span><span class="params">(a, b <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;<span class="keyword">if</span> a&gt;b&#123;<span class="keyword">return</span> a&#125;;<span class="keyword">return</span> b&#125;</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; <span class="built_in">len</span>(S); i++ &#123;</span><br><span class="line">        m[S[i]] = i</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">var</span> start, end = <span class="number">0</span>, <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> res []<span class="keyword">int</span></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; <span class="built_in">len</span>(S); i++ &#123;</span><br><span class="line">        <span class="comment">//更新当前区间结尾最大值</span></span><br><span class="line">        end = Max(end, m[S[i]])</span><br><span class="line">        <span class="comment">//走到当前区间结尾，当前区间结束</span></span><br><span class="line">        <span class="keyword">if</span> i==end &#123;</span><br><span class="line">            res = <span class="built_in">append</span>(res, end-start+<span class="number">1</span>)</span><br><span class="line">            start = i+<span class="number">1</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>代码意思很明确，多看看就明白了</p>
<h2 id="435-无重叠区间"><a href="#435-无重叠区间" class="headerlink" title="435. 无重叠区间"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/non-overlapping-intervals/" >435. 无重叠区间<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。</p>
<p>注意:</p>
<ul>
<li>可以认为区间的终点总是大于它的起点。</li>
<li>区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。</li>
</ul>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [ [<span class="number">1</span>,<span class="number">2</span>], [<span class="number">2</span>,<span class="number">3</span>], [<span class="number">3</span>,<span class="number">4</span>], [<span class="number">1</span>,<span class="number">3</span>] ]</span><br><span class="line"></span><br><span class="line">输出: <span class="number">1</span></span><br><span class="line"></span><br><span class="line">解释: 移除 [<span class="number">1</span>,<span class="number">3</span>] 后，剩下的区间没有重叠。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [ [<span class="number">1</span>,<span class="number">2</span>], [<span class="number">1</span>,<span class="number">2</span>], [<span class="number">1</span>,<span class="number">2</span>] ]</span><br><span class="line"></span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line"></span><br><span class="line">解释: 你需要移除两个 [<span class="number">1</span>,<span class="number">2</span>] 来使剩下的区间没有重叠。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [ [<span class="number">1</span>,<span class="number">2</span>], [<span class="number">2</span>,<span class="number">3</span>] ]</span><br><span class="line"></span><br><span class="line">输出: <span class="number">0</span></span><br><span class="line"></span><br><span class="line">解释: 你不需要移除任何区间，因为它们已经是无重叠的了。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>动态规划，其实和最长递增子序列是一样的</p>
<blockquote>
<p>和<a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/#646-%E6%9C%80%E9%95%BF%E6%95%B0%E5%AF%B9%E9%93%BE">最长数对链</a>一摸一样</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">eraseOverlapIntervals</span><span class="params">(<span class="keyword">int</span>[][] intervals)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (intervals==<span class="keyword">null</span> || intervals.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Arrays.sort(intervals,(a,b)-&gt;a[<span class="number">0</span>]-b[<span class="number">0</span>]);</span><br><span class="line">    <span class="keyword">int</span>[]dp=<span class="keyword">new</span> <span class="keyword">int</span>[intervals.length];</span><br><span class="line">    <span class="keyword">int</span> max=-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;intervals.length;i++) &#123;</span><br><span class="line">        dp[i]=<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;i;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(intervals[i][<span class="number">0</span>]&gt;=intervals[j][<span class="number">1</span>])&#123;</span><br><span class="line">                dp[i]=Math.max(dp[j]+<span class="number">1</span>,dp[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        max=Math.max(max,dp[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> intervals.length-max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>先根据左边界排个序，保证后面的不会覆盖前面的，然后反手求一下最长的无重叠区间长度，和最长递增子序列一样，最后用总长度减去这个最长的区间长度结果就是答案</p>
<p>171ms，8%，感觉快要过不了了。。。本来是是写的记忆化递归的，结果过不了。。。卡在倒数第二个case上</p>
<p><strong>记忆化递归写法</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">HashMap&lt;Pair,Integer&gt; cache=<span class="keyword">new</span> HashMap&lt;&gt;();<span class="comment">//TLE</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">eraseOverlapIntervals2</span><span class="params">(<span class="keyword">int</span>[][] intervals)</span> </span>&#123;</span><br><span class="line">    Arrays.sort(intervals,(a,b)-&gt;a[<span class="number">0</span>]-b[<span class="number">0</span>]);</span><br><span class="line">    <span class="keyword">return</span> intervals.length-dfs(intervals,<span class="number">0</span>,Integer.MIN_VALUE);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//背包问题,返回最多可以留下的区间</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span>[][] intervals,<span class="keyword">int</span> index,<span class="keyword">int</span> prev)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index==intervals.length) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Pair key=<span class="keyword">new</span> Pair(index,prev);</span><br><span class="line">    <span class="keyword">if</span> (cache.containsKey(key)) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache.get(key);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=dfs(intervals,index+<span class="number">1</span>,prev);</span><br><span class="line">    <span class="keyword">if</span> (intervals[index][<span class="number">0</span>]&gt;=prev) &#123;</span><br><span class="line">        res=Math.max(res,dfs(intervals,index+<span class="number">1</span>,intervals[index][<span class="number">1</span>])+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    cache.put(key,res);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>贪心，时间复杂度降低为线性</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">eraseOverlapIntervals</span><span class="params">(<span class="keyword">int</span>[][] intervals)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (intervals==<span class="keyword">null</span> || intervals.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//按照起点排序,重叠的时候选择保留结尾小的那一个</span></span><br><span class="line">    <span class="comment">//Arrays.sort(intervals,(a,b)-&gt;a[0]-b[0]); lambda初始化效率会低一点</span></span><br><span class="line">    Arrays.sort(intervals,<span class="keyword">new</span> Comparator&lt;<span class="keyword">int</span>[]&gt;()&#123;</span><br><span class="line">        <span class="meta">@Override</span></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">compare</span><span class="params">(<span class="keyword">int</span>[] a,<span class="keyword">int</span>[] b)</span></span>&#123;</span><br><span class="line">            <span class="keyword">return</span> a[<span class="number">0</span>]-b[<span class="number">0</span>];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;);</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> prev=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;intervals.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (intervals[i][<span class="number">0</span>]&gt;=intervals[prev][<span class="number">1</span>]) &#123;</span><br><span class="line">            res++;</span><br><span class="line">            prev=i;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(intervals[i][<span class="number">1</span>]&lt;intervals[prev][<span class="number">1</span>])&#123;</span><br><span class="line">            prev=i; <span class="comment">//选择结尾小的那一个</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> intervals.length-res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>按照起点排序，在重叠的时候优先选择结尾小的哪一个，这样就可能得到更多的区间组合</p>
<h2 id="1288-删除被覆盖区间"><a href="#1288-删除被覆盖区间" class="headerlink" title="1288. 删除被覆盖区间"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/remove-covered-intervals/" >1288. 删除被覆盖区间<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。</p>
<p>只有当 <code>c &lt;= a</code> 且 <code>b &lt;= d</code> 时，我们才认为区间 <code>[a,b)</code> 被区间 <code>[c,d)</code> 覆盖。</p>
<p>在完成所有删除操作后，请你返回列表中剩余区间的数目。</p>
<p><strong>示例：</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入：intervals = [[<span class="number">1</span>,<span class="number">4</span>],[<span class="number">3</span>,<span class="number">6</span>],[<span class="number">2</span>,<span class="number">8</span>]]</span><br><span class="line">输出：<span class="number">2</span></span><br><span class="line">解释：区间 [<span class="number">3</span>,<span class="number">6</span>] 被区间 [<span class="number">2</span>,<span class="number">8</span>] 覆盖，所以它被删除了。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong>​​​​​​</p>
<ul>
<li>  <code>1 &lt;= intervals.length &lt;= 1000</code></li>
<li>  <code>0 &lt;= intervals[i][0] &lt; intervals[i][1] &lt;= 10^5</code></li>
<li>  对于所有的 <code>i != j</code>：<code>intervals[i] != intervals[j]</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>思路比较直白</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">removeCoveredIntervals</span><span class="params">(intervals [][]<span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    sort.Slice(intervals, <span class="function"><span class="keyword">func</span> <span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">        <span class="keyword">if</span> intervals[i][<span class="number">0</span>] == intervals[j][<span class="number">0</span>] &#123;</span><br><span class="line">            <span class="keyword">return</span> intervals[i][<span class="number">1</span>] &gt; intervals[j][<span class="number">1</span>]</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> intervals[i][<span class="number">0</span>] &lt; intervals[j][<span class="number">0</span>]</span><br><span class="line">    &#125;)</span><br><span class="line">    <span class="keyword">var</span> Max = <span class="function"><span class="keyword">func</span><span class="params">(a, b <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;<span class="keyword">if</span> a&gt;b &#123;<span class="keyword">return</span> a&#125;;<span class="keyword">return</span> b&#125;</span><br><span class="line">    <span class="keyword">var</span> count = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> maxRight = intervals[<span class="number">0</span>][<span class="number">1</span>]</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">1</span>; i &lt; <span class="built_in">len</span>(intervals); i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> intervals[i][<span class="number">1</span>] &lt;= maxRight &#123;</span><br><span class="line">            count++</span><br><span class="line">        &#125;</span><br><span class="line">        maxRight = Max(maxRight, intervals[i][<span class="number">1</span>])</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">len</span>(intervals)-count</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="452-用最少数量的箭引爆气球"><a href="#452-用最少数量的箭引爆气球" class="headerlink" title="452. 用最少数量的箭引爆气球"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/" >452. 用最少数量的箭引爆气球<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在10<sup>4</sup>个气球。</p>
<p>一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 x<sub style="display: inline;">start，</sub>x<sub style="display: inline;">end，</sub> 且满足  x<sub style="display: inline;">start</sub> ≤ x ≤ x<sub style="display: inline;">end，</sub>则该气球会被引爆<sub style="display: inline;">。</sub>可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。</p>
<p><strong>Example:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line">[[<span class="number">10</span>,<span class="number">16</span>], [<span class="number">2</span>,<span class="number">8</span>], [<span class="number">1</span>,<span class="number">6</span>], [<span class="number">7</span>,<span class="number">12</span>]]</span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line"><span class="number">2</span></span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line">对于该样例，我们可以在x = <span class="number">6</span>（射爆[<span class="number">2</span>,<span class="number">8</span>],[<span class="number">1</span>,<span class="number">6</span>]两个气球）和 x = <span class="number">11</span>（射爆另外两个气球）。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>和前面几题一样，按照起点排序，发生重叠时记录小的Xend，实际上end的含义就是当前这一箭能射穿前面所有气球的最远距离，后面的气球如果大于这个距离就需要加一箭，否则就可以一并射穿</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">findMinArrowShots</span><span class="params">(points [][]<span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">len</span>(points) &lt;= <span class="number">0</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">    &#125;</span><br><span class="line">    sort.Slice(points, <span class="function"><span class="keyword">func</span><span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">        <span class="keyword">return</span> points[i][<span class="number">0</span>] &lt; points[j][<span class="number">0</span>]</span><br><span class="line">    &#125;)</span><br><span class="line">    <span class="keyword">var</span> end = points[<span class="number">0</span>][<span class="number">1</span>]</span><br><span class="line">    <span class="keyword">var</span> res = <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">1</span>; i &lt; <span class="built_in">len</span>(points); i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> points[i][<span class="number">0</span>] &gt; end &#123;</span><br><span class="line">            res++</span><br><span class="line">            end = points[i][<span class="number">1</span>]</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            end = Min(end, points[i][<span class="number">1</span>])</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br><span class="line">​</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Min</span><span class="params">(a, b <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> a &gt; b &#123;</span><br><span class="line">        <span class="keyword">return</span> b</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> a</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>按照终点排序</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">findMinArrowShots</span><span class="params">(points [][]<span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">len</span>(points) &lt;= <span class="number">0</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">    &#125;</span><br><span class="line">    sort.Slice(points, <span class="function"><span class="keyword">func</span><span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">        <span class="keyword">return</span> points[i][<span class="number">1</span>] &lt; points[j][<span class="number">1</span>]</span><br><span class="line">    &#125;)</span><br><span class="line">    <span class="keyword">var</span> end = points[<span class="number">0</span>][<span class="number">1</span>]</span><br><span class="line">    <span class="keyword">var</span> res = <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">1</span>; i &lt; <span class="built_in">len</span>(points); i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> points[i][<span class="number">0</span>] &gt; end &#123;</span><br><span class="line">            res++</span><br><span class="line">            end = points[i][<span class="number">1</span>]</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Min</span><span class="params">(a, b <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> a &gt; b &#123;</span><br><span class="line">        <span class="keyword">return</span> b</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> a</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1024-视频拼接"><a href="#1024-视频拼接" class="headerlink" title="1024. 视频拼接"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/video-stitching/" >1024. 视频拼接<i class="fas fa-external-link-alt"></i></a></h2><p>你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。</p>
<p>视频片段 <code>clips[i]</code> 都用区间进行表示：开始于 <code>clips[i][0]</code> 并于 <code>clips[i][1]</code> 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 <code>[0, 1] + [1, 3] + [3, 7]</code> 三部分。</p>
<p>我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：clips = [[<span class="number">0</span>,<span class="number">2</span>],[<span class="number">4</span>,<span class="number">6</span>],[<span class="number">8</span>,<span class="number">10</span>],[<span class="number">1</span>,<span class="number">9</span>],[<span class="number">1</span>,<span class="number">5</span>],[<span class="number">5</span>,<span class="number">9</span>]], T = <span class="number">10</span></span><br><span class="line">输出：<span class="number">3</span></span><br><span class="line">解释：</span><br><span class="line">我们选中 [<span class="number">0</span>,<span class="number">2</span>], [<span class="number">8</span>,<span class="number">10</span>], [<span class="number">1</span>,<span class="number">9</span>] 这三个片段。</span><br><span class="line">然后，按下面的方案重制比赛片段：</span><br><span class="line">将 [<span class="number">1</span>,<span class="number">9</span>] 再剪辑为 [<span class="number">1</span>,<span class="number">2</span>] + [<span class="number">2</span>,<span class="number">8</span>] + [<span class="number">8</span>,<span class="number">9</span>] 。</span><br><span class="line">现在我们手上有 [<span class="number">0</span>,<span class="number">2</span>] + [<span class="number">2</span>,<span class="number">8</span>] + [<span class="number">8</span>,<span class="number">10</span>]，而这些涵盖了整场比赛 [<span class="number">0</span>, <span class="number">10</span>]。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：clips = [[<span class="number">0</span>,<span class="number">1</span>],[<span class="number">1</span>,<span class="number">2</span>]], T = <span class="number">5</span></span><br><span class="line">输出：-<span class="number">1</span></span><br><span class="line">解释：</span><br><span class="line">我们无法只用 [<span class="number">0</span>,<span class="number">1</span>] 和 [<span class="number">0</span>,<span class="number">2</span>] 覆盖 [<span class="number">0</span>,<span class="number">5</span>] 的整个过程。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：clips = [[<span class="number">0</span>,<span class="number">1</span>],[<span class="number">6</span>,<span class="number">8</span>],[<span class="number">0</span>,<span class="number">2</span>],[<span class="number">5</span>,<span class="number">6</span>],[<span class="number">0</span>,<span class="number">4</span>],[<span class="number">0</span>,<span class="number">3</span>],[<span class="number">6</span>,<span class="number">7</span>],[<span class="number">1</span>,<span class="number">3</span>],[<span class="number">4</span>,<span class="number">7</span>],[<span class="number">1</span>,<span class="number">4</span>],[<span class="number">2</span>,<span class="number">5</span>],[<span class="number">2</span>,<span class="number">6</span>],[<span class="number">3</span>,<span class="number">4</span>],[<span class="number">4</span>,<span class="number">5</span>],[<span class="number">5</span>,<span class="number">7</span>],[<span class="number">6</span>,<span class="number">9</span>]], T = <span class="number">9</span></span><br><span class="line">输出：<span class="number">3</span></span><br><span class="line">解释： </span><br><span class="line">我们选取片段 [<span class="number">0</span>,<span class="number">4</span>], [<span class="number">4</span>,<span class="number">7</span>] 和 [<span class="number">6</span>,<span class="number">9</span>] 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：clips = [[<span class="number">0</span>,<span class="number">4</span>],[<span class="number">2</span>,<span class="number">8</span>]], T = <span class="number">5</span></span><br><span class="line">输出：<span class="number">2</span></span><br><span class="line">解释：</span><br><span class="line">注意，你可能录制超过比赛结束时间的视频。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= clips.length &lt;= 100</code></li>
<li><code>0 &lt;= clips[i][0], clips[i][1] &lt;= 100</code></li>
<li><code>0 &lt;= T &lt;= 100</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>感觉这个贪心还是很经典的，很多题都是这个思路，上面的 跳跃游戏2，包括172周赛的最后一题，都是这个类似的区间覆盖问题</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">videoStitching</span><span class="params">(<span class="keyword">int</span>[][] clips, <span class="keyword">int</span> T)</span> </span>&#123;</span><br><span class="line">    Arrays.sort(clips,(a,b)-&gt;a[<span class="number">0</span>]-b[<span class="number">0</span>]);</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>,res=<span class="number">0</span>,last=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;clips.length) &#123;</span><br><span class="line">        <span class="keyword">int</span> temp=last;</span><br><span class="line">        <span class="keyword">while</span>(i&lt;clips.length&amp;&amp;clips[i][<span class="number">0</span>]&lt;=temp) &#123;</span><br><span class="line">            last=Math.max(last,clips[i][<span class="number">1</span>]);</span><br><span class="line">            i++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (last==temp) &#123; <span class="comment">//没有找到能覆盖的</span></span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        res++;</span><br><span class="line">        <span class="keyword">if</span> (last&gt;=T) &#123;</span><br><span class="line">            <span class="keyword">return</span> res;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>首先按照左边界排序，然后找的时候<strong>每次都在序列中找能覆盖<code>overlap</code>上一次右边界的最长区间</strong> ，第一次覆盖其实就是找的左边界能覆盖0的最长的区间，然后下一次就要找能覆盖这个区间右边界的最长的区间。最终的结果就是最少的区间数目，正确性这里其实思考一下就知道了，每次都选择最优区间，对后面的选择没有负面影响，具体如何证明还是留给大佬们吧</p>
<h2 id="406-根据身高重建队列"><a href="#406-根据身高重建队列" class="headerlink" title="406. 根据身高重建队列"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/queue-reconstruction-by-height/" >406. 根据身高重建队列<i class="fas fa-external-link-alt"></i></a></h2><p>假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对<code>(h, k)</code>表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。</p>
<p>注意：<br>总人数少于1100人。</p>
<p><strong>示例</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line">[[<span class="number">7</span>,<span class="number">0</span>], [<span class="number">4</span>,<span class="number">4</span>], [<span class="number">7</span>,<span class="number">1</span>], [<span class="number">5</span>,<span class="number">0</span>], [<span class="number">6</span>,<span class="number">1</span>], [<span class="number">5</span>,<span class="number">2</span>]]</span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line">[[<span class="number">5</span>,<span class="number">0</span>], [<span class="number">7</span>,<span class="number">0</span>], [<span class="number">5</span>,<span class="number">2</span>], [<span class="number">6</span>,<span class="number">1</span>], [<span class="number">4</span>,<span class="number">4</span>], [<span class="number">7</span>,<span class="number">1</span>]]</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>贪心，没想出来</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[][] reconstructQueue(<span class="keyword">int</span>[][] people) &#123;</span><br><span class="line">    <span class="keyword">if</span> (people==<span class="keyword">null</span> ||people.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">0</span>][<span class="number">0</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    List&lt;<span class="keyword">int</span>[]&gt; res=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    Arrays.sort(people,(p1,p2)-&gt;p1[<span class="number">0</span>]!=p2[<span class="number">0</span>]?p2[<span class="number">0</span>]-p1[<span class="number">0</span>]:p1[<span class="number">1</span>]-p2[<span class="number">1</span>]);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;people.length;i++) &#123;</span><br><span class="line">        res.add(people[i][<span class="number">1</span>],people[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.toArray(<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">0</span>][<span class="number">0</span>]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>首先对身高h降序，k升序进行排列得到，然后将元素<code>（h，k）</code>插入前面比它大的元素中的第k个位置，保证该元素前面有k个比当前元素大的，使之合法，<strong>后面的比它矮的元素的移动对前面其实的没有任何影响</strong>，这个算法的正确性很容易想到，身高高的人是看不到身高矮的人的~，也就是身高矮的人在身高高的人前或后对身高高的人是没有任何影响的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">[<span class="number">7</span>,<span class="number">0</span>] [<span class="number">7</span>,<span class="number">1</span>] [<span class="number">6</span>,<span class="number">1</span>] [<span class="number">5</span>,<span class="number">0</span>] [<span class="number">5</span>,<span class="number">2</span>] [<span class="number">4</span>,<span class="number">4</span>]</span><br><span class="line"></span><br><span class="line">[]                (<span class="number">7</span>,<span class="number">0</span>) -&gt; []</span><br><span class="line"><span class="number">0</span>                 (<span class="number">7</span>,<span class="number">1</span>) -&gt; [<span class="number">7</span>,<span class="number">0</span>]</span><br><span class="line"><span class="number">0</span> <span class="number">1</span>               (<span class="number">6</span>,<span class="number">1</span>) -&gt; [<span class="number">7</span>,<span class="number">0</span>] [<span class="number">7</span>,<span class="number">1</span>]</span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">2</span>             (<span class="number">5</span>,<span class="number">0</span>) -&gt; [<span class="number">7</span>,<span class="number">0</span>] [<span class="number">6</span>,<span class="number">1</span>] [<span class="number">7</span>,<span class="number">1</span>]</span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">2</span> <span class="number">3</span>           (<span class="number">5</span>,<span class="number">2</span>) -&gt; [<span class="number">5</span>,<span class="number">0</span>] [<span class="number">7</span>,<span class="number">0</span>] [<span class="number">6</span>,<span class="number">1</span>] [<span class="number">7</span>,<span class="number">1</span>]</span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">2</span> <span class="number">3</span> <span class="number">4</span>         (<span class="number">4</span>,<span class="number">4</span>) -&gt; [<span class="number">5</span>,<span class="number">0</span>] [<span class="number">7</span>,<span class="number">0</span>] [<span class="number">5</span>,<span class="number">2</span>] [<span class="number">6</span>,<span class="number">1</span>] [<span class="number">7</span>,<span class="number">1</span>]</span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">2</span> <span class="number">3</span> <span class="number">4</span> <span class="number">5</span>                [<span class="number">5</span>,<span class="number">0</span>] [<span class="number">7</span>,<span class="number">0</span>] [<span class="number">5</span>,<span class="number">2</span>] [<span class="number">6</span>,<span class="number">1</span>] [<span class="number">4</span>,<span class="number">4</span>] [<span class="number">7</span>,<span class="number">1</span>]</span><br></pre></td></tr></table></figure>

<h2 id="1262-可被三整除的最大和"><a href="#1262-可被三整除的最大和" class="headerlink" title="1262. 可被三整除的最大和"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/greatest-sum-divisible-by-three/" >1262. 可被三整除的最大和<i class="fas fa-external-link-alt"></i></a></h2><p>给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">3</span>,<span class="number">6</span>,<span class="number">5</span>,<span class="number">1</span>,<span class="number">8</span>]</span><br><span class="line">输出：<span class="number">18</span></span><br><span class="line">解释：选出数字 <span class="number">3</span>, <span class="number">6</span>, <span class="number">1</span> 和 <span class="number">8</span>，它们的和是 <span class="number">18</span>（可被 <span class="number">3</span> 整除的最大和）。</span><br></pre></td></tr></table></figure>


<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">4</span>]</span><br><span class="line">输出：<span class="number">0</span></span><br><span class="line">解释：<span class="number">4</span> 不能被 <span class="number">3</span> 整除，所以无法选出数字，返回 <span class="number">0</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">4</span>]</span><br><span class="line">输出：<span class="number">12</span></span><br><span class="line">解释：选出数字 <span class="number">1</span>, <span class="number">3</span>, <span class="number">4</span> 以及 <span class="number">4</span>，它们的和是 <span class="number">12</span>（可被 <span class="number">3</span> 整除的最大和）。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= nums.length &lt;= 4 * 10^4</code></li>
<li><code>1 &lt;= nums[i] &lt;= 10^4</code></li>
</ul>
<p><strong>解法三</strong></p>
<p>O(NlogN)贪心，最优解法应该是dp，放在dp<a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/">专题中</a></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxSumDivThree3</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    List&lt;Integer&gt; one=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    List&lt;Integer&gt; two=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> n:nums) &#123;</span><br><span class="line">        sum+=n;</span><br><span class="line">        <span class="keyword">if</span> (n%<span class="number">3</span>==<span class="number">1</span>) one.add(n);</span><br><span class="line">        <span class="keyword">if</span> (n%<span class="number">3</span>==<span class="number">2</span>) two.add(n);</span><br><span class="line">    &#125;</span><br><span class="line">    Collections.sort(one);</span><br><span class="line">    Collections.sort(two);</span><br><span class="line">    <span class="keyword">if</span> (sum%<span class="number">3</span>==<span class="number">1</span>) &#123; <span class="comment">//移除一个余数为1的 或者两个余数为2的</span></span><br><span class="line">        <span class="keyword">return</span> Math.max(one.size()&gt;=<span class="number">1</span>?sum-one.get(<span class="number">0</span>):<span class="number">0</span>,two.size()&gt;=<span class="number">2</span>?sum-two.get(<span class="number">0</span>)-two.get(<span class="number">1</span>):<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (sum%<span class="number">3</span>==<span class="number">2</span>) &#123; <span class="comment">//移除一个余数为2 或者两个余数为1的</span></span><br><span class="line">        <span class="keyword">return</span> Math.max(two.size()&gt;=<span class="number">1</span>?sum-two.get(<span class="number">0</span>):<span class="number">0</span>,one.size()&gt;=<span class="number">2</span>?sum-one.get(<span class="number">0</span>)-one.get(<span class="number">1</span>):<span class="number">0</span>);   </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>如果总和%3=1我们就可以移除数组中%3=1的最小那个或者移除两个%3=2的最小的，同理，总和%3=2，我们可以移除一个最小的%2=0的元素，或者移除两个%2=1的最小元素</p>
<p>这里我们需要记录的仅仅是数组中%3=1和%3=2的最小的4个值就ok，其实不用排序就可以，直接O(N)遍历就行，嫌麻烦没改，后面有时间来改改</p>
<p><strong>解法二</strong></p>
<p>履行上面的承诺，改好了一版O(N)的贪心解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxSumDivThree</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> M=<span class="number">0x3f3f3f3f</span>;</span><br><span class="line">    <span class="comment">//余1最小值</span></span><br><span class="line">    <span class="keyword">int</span> min1_0=M,min1_1=M;</span><br><span class="line">    <span class="comment">//余2最小值</span></span><br><span class="line">    <span class="keyword">int</span> min2_0=M,min2_1=M;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++)&#123;</span><br><span class="line">        sum+=nums[i];</span><br><span class="line">        <span class="keyword">if</span>(nums[i]%<span class="number">3</span>==<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(nums[i]&lt;=min1_0)&#123;</span><br><span class="line">                min1_1=min1_0; <span class="comment">//更新次小值</span></span><br><span class="line">                min1_0=nums[i]; <span class="comment">//更新最小值</span></span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span>(nums[i]&lt;=min1_1)&#123;</span><br><span class="line">                min1_1=nums[i]; <span class="comment">//更新次小值</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(nums[i]%<span class="number">3</span>==<span class="number">2</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(nums[i]&lt;=min2_0)&#123;</span><br><span class="line">                min2_1=min2_0;</span><br><span class="line">                min2_0=nums[i];</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span>(nums[i]&lt;=min2_1)&#123;</span><br><span class="line">                min2_1=nums[i];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(sum%<span class="number">3</span>==<span class="number">1</span>) <span class="keyword">return</span> sum-Math.min(min2_0+min2_1,min1_0);</span><br><span class="line">    <span class="keyword">if</span>(sum%<span class="number">3</span>==<span class="number">2</span>) <span class="keyword">return</span> sum-Math.min(min1_0+min1_1,min2_0);</span><br><span class="line">    <span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="5172-形成三的最大倍数"><a href="#5172-形成三的最大倍数" class="headerlink" title="5172. 形成三的最大倍数"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/largest-multiple-of-three/" >5172. 形成三的最大倍数<i class="fas fa-external-link-alt"></i></a></h2><p>给你一个整数数组 <code>digits</code>，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。</p>
<p>由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。</p>
<p>如果无法得到答案，请返回一个空字符串。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：digits = [<span class="number">8</span>,<span class="number">1</span>,<span class="number">9</span>]</span><br><span class="line">输出：<span class="string">&quot;981&quot;</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：digits = [<span class="number">8</span>,<span class="number">6</span>,<span class="number">7</span>,<span class="number">1</span>,<span class="number">0</span>]</span><br><span class="line">输出：<span class="string">&quot;8760&quot;</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：digits = [<span class="number">1</span>]</span><br><span class="line">输出：<span class="string">&quot;&quot;</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：digits = [<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]</span><br><span class="line">输出：<span class="string">&quot;0&quot;</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= digits.length &lt;= 10^4</li>
<li>0 &lt;= digits[i] &lt;= 9</li>
<li>返回的结果不应包含不必要的前导零。</li>
</ul>
<p><strong>解法一</strong></p>
<p>177周赛的T4，时隔多日，周赛又出了这一题，和上面一样，思路差不多的，需要优先考虑只删除一个的情况</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">largestMultipleOfThree</span><span class="params">(<span class="keyword">int</span>[] digits)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span>[] freq=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10</span>];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;digits.length;i++) &#123;</span><br><span class="line">        sum+=digits[i];</span><br><span class="line">        freq[digits[i]]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(sum==<span class="number">0</span>) <span class="keyword">return</span> <span class="string">&quot;0&quot;</span>;</span><br><span class="line">    <span class="comment">//删除一个余1的或者两个余2的,优先删除一个余1的</span></span><br><span class="line">    <span class="comment">//删除1个得到的结果肯定比删除2个大</span></span><br><span class="line">    <span class="keyword">if</span>(sum%<span class="number">3</span>==<span class="number">1</span>)&#123; </span><br><span class="line">        <span class="keyword">if</span>(!deleteMin(freq,<span class="number">1</span>))&#123; </span><br><span class="line">            deleteMin(freq,<span class="number">2</span>);</span><br><span class="line">            deleteMin(freq,<span class="number">2</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(sum%<span class="number">3</span>==<span class="number">2</span>)&#123; <span class="comment">//删除一个余2的或者两个余1的</span></span><br><span class="line">        <span class="keyword">if</span>(!deleteMin(freq,<span class="number">2</span>))&#123;</span><br><span class="line">            deleteMin(freq,<span class="number">1</span>);</span><br><span class="line">            deleteMin(freq,<span class="number">1</span>);</span><br><span class="line">        &#125;   </span><br><span class="line">    &#125;</span><br><span class="line">    StringBuilder res=<span class="keyword">new</span> StringBuilder();</span><br><span class="line">    <span class="comment">//逆序构建结果</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">9</span>;i&gt;=<span class="number">0</span>;i--)&#123;</span><br><span class="line">        <span class="keyword">int</span> count=freq[i];</span><br><span class="line">        <span class="keyword">while</span>(count-- &gt;<span class="number">0</span>)&#123;</span><br><span class="line">            res.append(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.toString();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">deleteMin</span><span class="params">(<span class="keyword">int</span>[] freq,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=y;i&lt;<span class="number">9</span>;i+=<span class="number">3</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (freq[i]!=<span class="number">0</span>) &#123;</span><br><span class="line">            freq[i]--;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1111-有效括号的嵌套深度"><a href="#1111-有效括号的嵌套深度" class="headerlink" title="1111. 有效括号的嵌套深度"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/" >1111. 有效括号的嵌套深度<i class="fas fa-external-link-alt"></i></a></h2><p>迷惑题，不想粘题目了</p>
<p><strong>解法一</strong></p>
<p>按照深度的奇偶划分两个子串。。。。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] maxDepthAfterSplit(String seq) &#123;</span><br><span class="line">    <span class="comment">//Deque&lt;Character&gt; stack=new ArrayDeque&lt;&gt;();</span></span><br><span class="line">    <span class="keyword">int</span> depth=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span>[] res=<span class="keyword">new</span> <span class="keyword">int</span>[seq.length()];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;seq.length();i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(seq.charAt(i)==<span class="string">&#x27;(&#x27;</span>)&#123;</span><br><span class="line">            res[i]=depth++%<span class="number">2</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//根据左括号奇偶判断</span></span><br><span class="line">            res[i]=--depth%<span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1353-最多可以参加的会议数目"><a href="#1353-最多可以参加的会议数目" class="headerlink" title="1353. 最多可以参加的会议数目"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-number-of-events-that-can-be-attended/" >1353. 最多可以参加的会议数目<i class="fas fa-external-link-alt"></i></a></h2><p>给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。</p>
<p>你可以在满足 startDayi &lt;= d &lt;= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。</p>
<p>请你返回你可以参加的 最大 会议数目。</p>
<p><strong>示例 1：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://s1.ax1x.com/2020/04/17/JELWN9.png"
                      alt="JELWN9.png"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：events = [[<span class="number">1</span>,<span class="number">2</span>],[<span class="number">2</span>,<span class="number">3</span>],[<span class="number">3</span>,<span class="number">4</span>]]</span><br><span class="line">输出：<span class="number">3</span></span><br><span class="line">解释：你可以参加所有的三个会议。</span><br><span class="line">安排会议的一种方案如上图。</span><br><span class="line">第 <span class="number">1</span> 天参加第一个会议。</span><br><span class="line">第 <span class="number">2</span> 天参加第二个会议。</span><br><span class="line">第 <span class="number">3</span> 天参加第三个会议。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：events= [[<span class="number">1</span>,<span class="number">2</span>],[<span class="number">2</span>,<span class="number">3</span>],[<span class="number">3</span>,<span class="number">4</span>],[<span class="number">1</span>,<span class="number">2</span>]]</span><br><span class="line">输出：<span class="number">4</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：events = [[<span class="number">1</span>,<span class="number">4</span>],[<span class="number">4</span>,<span class="number">4</span>],[<span class="number">2</span>,<span class="number">2</span>],[<span class="number">3</span>,<span class="number">4</span>],[<span class="number">1</span>,<span class="number">1</span>]]</span><br><span class="line">输出：<span class="number">4</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：events = [[<span class="number">1</span>,<span class="number">100000</span>]]</span><br><span class="line">输出：<span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 5：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：events = [[<span class="number">1</span>,<span class="number">1</span>],[<span class="number">1</span>,<span class="number">2</span>],[<span class="number">1</span>,<span class="number">3</span>],[<span class="number">1</span>,<span class="number">4</span>],[<span class="number">1</span>,<span class="number">5</span>],[<span class="number">1</span>,<span class="number">6</span>],[<span class="number">1</span>,<span class="number">7</span>]]</span><br><span class="line">输出：<span class="number">7</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= events.length &lt;= 10^5</code></li>
<li><code>events[i].length == 2</code></li>
<li><code>1 &lt;= events[i][0] &lt;= events[i][1] &lt;= 10^5</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>暴力贪心</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//[[1,4],[4,4],[2,2],[3,4],[1,1]]</span></span><br><span class="line"><span class="comment">// 1,1  2,2  1,4  3,4  4,4</span></span><br><span class="line"><span class="comment">// 暴力贪心，按结束时间排序，优先安排结束时间短的，O(N^2)</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxEvents</span><span class="params">(<span class="keyword">int</span>[][] events)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(events==<span class="keyword">null</span> || events.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    Arrays.sort(events,(e1,e2)-&gt;e1[<span class="number">1</span>]-e2[<span class="number">1</span>]);</span><br><span class="line">    <span class="comment">//当天有没有安排会议</span></span><br><span class="line">    HashSet&lt;Integer&gt; set=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;events.length;i++)&#123;</span><br><span class="line">        <span class="keyword">int</span> start=events[i][<span class="number">0</span>];</span><br><span class="line">        <span class="keyword">int</span> end=events[i][<span class="number">1</span>];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=start;j&lt;=end;j++)&#123; <span class="comment">//在对应时间段内进行安排</span></span><br><span class="line">            <span class="keyword">if</span>(!set.contains(j))&#123;</span><br><span class="line">                set.add(j);</span><br><span class="line">                count++;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//优先队列优化，NlogN</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxEvents</span><span class="params">(<span class="keyword">int</span>[][] events)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(events==<span class="keyword">null</span> || events.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    Arrays.sort(events,(e1,e2)-&gt;e1[<span class="number">0</span>]-e2[<span class="number">0</span>]);</span><br><span class="line">    <span class="comment">//结束时间构建小根堆</span></span><br><span class="line">    PriorityQueue&lt;Integer&gt; pq=<span class="keyword">new</span> PriorityQueue&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> index=<span class="number">0</span>,res=<span class="number">0</span>,n=events.length;</span><br><span class="line">    <span class="keyword">int</span> curDay=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(index&lt;n || !pq.isEmpty())&#123;</span><br><span class="line">        <span class="comment">//将当天开始的会议的结束时间加入小根堆</span></span><br><span class="line">        <span class="keyword">while</span>(index&lt;n &amp;&amp; curDay==events[index][<span class="number">0</span>])&#123;</span><br><span class="line">            pq.add(events[index++][<span class="number">1</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//将过期会议的移除</span></span><br><span class="line">        <span class="keyword">while</span>(!pq.isEmpty() &amp;&amp; pq.peek()&lt;curDay)&#123;</span><br><span class="line">            pq.poll();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//优先选择结束时间最短的</span></span><br><span class="line">        <span class="keyword">if</span>(!pq.isEmpty())&#123;</span><br><span class="line">            pq.poll();</span><br><span class="line">            res++;</span><br><span class="line">        &#125;</span><br><span class="line">        curDay++; <span class="comment">//安排下一天</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="134-加油站"><a href="#134-加油站" class="headerlink" title="134. 加油站"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/gas-station/" >134. 加油站<i class="fas fa-external-link-alt"></i></a></h2><p>在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。</p>
<p>你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。</p>
<p>如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。</p>
<p><strong>说明:</strong> </p>
<ul>
<li>如果题目有解，该答案即为唯一答案。</li>
<li>输入数组均为非空数组，且长度相同。</li>
<li>输入数组中的元素均为非负数。</li>
</ul>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: </span><br><span class="line">gas  = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>]</span><br><span class="line">cost = [<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>,<span class="number">1</span>,<span class="number">2</span>]</span><br><span class="line"></span><br><span class="line">输出: <span class="number">3</span></span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line">从 <span class="number">3</span> 号加油站(索引为 <span class="number">3</span> 处)出发，可获得 <span class="number">4</span> 升汽油。此时油箱有 = <span class="number">0</span> + <span class="number">4</span> = <span class="number">4</span> 升汽油</span><br><span class="line">开往 <span class="number">4</span> 号加油站，此时油箱有 <span class="number">4</span> - <span class="number">1</span> + <span class="number">5</span> = <span class="number">8</span> 升汽油</span><br><span class="line">开往 <span class="number">0</span> 号加油站，此时油箱有 <span class="number">8</span> - <span class="number">2</span> + <span class="number">1</span> = <span class="number">7</span> 升汽油</span><br><span class="line">开往 <span class="number">1</span> 号加油站，此时油箱有 <span class="number">7</span> - <span class="number">3</span> + <span class="number">2</span> = <span class="number">6</span> 升汽油</span><br><span class="line">开往 <span class="number">2</span> 号加油站，此时油箱有 <span class="number">6</span> - <span class="number">4</span> + <span class="number">3</span> = <span class="number">5</span> 升汽油</span><br><span class="line">开往 <span class="number">3</span> 号加油站，你需要消耗 <span class="number">5</span> 升汽油，正好足够你返回到 <span class="number">3</span> 号加油站。</span><br><span class="line">因此，<span class="number">3</span> 可为起始索引。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: </span><br><span class="line">gas  = [<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>]</span><br><span class="line">cost = [<span class="number">3</span>,<span class="number">4</span>,<span class="number">3</span>]</span><br><span class="line"></span><br><span class="line">输出: -<span class="number">1</span></span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line">你不能从 <span class="number">0</span> 号或 <span class="number">1</span> 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。</span><br><span class="line">我们从 <span class="number">2</span> 号加油站出发，可以获得 <span class="number">4</span> 升汽油。 此时油箱有 = <span class="number">0</span> + <span class="number">4</span> = <span class="number">4</span> 升汽油</span><br><span class="line">开往 <span class="number">0</span> 号加油站，此时油箱有 <span class="number">4</span> - <span class="number">3</span> + <span class="number">2</span> = <span class="number">3</span> 升汽油</span><br><span class="line">开往 <span class="number">1</span> 号加油站，此时油箱有 <span class="number">3</span> - <span class="number">3</span> + <span class="number">3</span> = <span class="number">3</span> 升汽油</span><br><span class="line">你无法返回 <span class="number">2</span> 号加油站，因为返程需要消耗 <span class="number">4</span> 升汽油，但是你的油箱只有 <span class="number">3</span> 升汽油。</span><br><span class="line">因此，无论怎样，你都不可能绕环路行驶一周。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">canCompleteCircuit</span><span class="params">(gas []<span class="keyword">int</span>, cost []<span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    n:=<span class="built_in">len</span>(gas)</span><br><span class="line">    curGas:=<span class="number">0</span> <span class="comment">//当前油量</span></span><br><span class="line">    start:=<span class="number">0</span> <span class="comment">//起点</span></span><br><span class="line">    total:=<span class="number">0</span> <span class="comment">//gas和cost之差,小于0的话肯定无法绕圈</span></span><br><span class="line">    <span class="keyword">for</span> i:=start;i&lt;n;i++&#123;</span><br><span class="line">        curGas+=(gas[i]-cost[i])</span><br><span class="line">        total+=(gas[i]-cost[i])</span><br><span class="line">        <span class="comment">//油量不够，i无法继续前进到i+1,说明从start~i无法绕环</span></span><br><span class="line">        <span class="keyword">if</span> curGas&lt;<span class="number">0</span>&#123; </span><br><span class="line">            start=i+<span class="number">1</span></span><br><span class="line">            curGas=<span class="number">0</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> total&lt;<span class="number">0</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> start</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1046-最后一块石头的重量"><a href="#1046-最后一块石头的重量" class="headerlink" title="1046. 最后一块石头的重量"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/last-stone-weight/" >1046. 最后一块石头的重量<i class="fas fa-external-link-alt"></i></a></h2><p>有一堆石头，每块石头的重量都是正整数。</p>
<p>每一回合，从中选出两块 <strong>最重的</strong> 石头，然后将它们一起粉碎。假设石头的重量分别为 <code>x</code> 和 <code>y</code>，且 <code>x &lt;= y</code>。那么粉碎的可能结果如下：</p>
<ul>
<li>如果 <code>x == y</code>，那么两块石头都会被完全粉碎；</li>
<li>如果 <code>x != y</code>，那么重量为 <code>x</code> 的石头将会完全粉碎，而重量为 <code>y</code> 的石头新重量为 <code>y-x</code>。</li>
</ul>
<p>最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 <code>0</code>。</p>
<p><strong>示例：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">2</span>,<span class="number">7</span>,<span class="number">4</span>,<span class="number">1</span>,<span class="number">8</span>,<span class="number">1</span>]</span><br><span class="line">输出：<span class="number">1</span></span><br><span class="line">解释：</span><br><span class="line">先选出 <span class="number">7</span> 和 <span class="number">8</span>，得到 <span class="number">1</span>，所以数组转换为 [<span class="number">2</span>,<span class="number">4</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>]，</span><br><span class="line">再选出 <span class="number">2</span> 和 <span class="number">4</span>，得到 <span class="number">2</span>，所以数组转换为 [<span class="number">2</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>]，</span><br><span class="line">接着是 <span class="number">2</span> 和 <span class="number">1</span>，得到 <span class="number">1</span>，所以数组转换为 [<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>]，</span><br><span class="line">最后选出 <span class="number">1</span> 和 <span class="number">1</span>，得到 <span class="number">0</span>，最终数组转换为 [<span class="number">1</span>]，这就是最后剩下那块石头的重量。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>1 &lt;= stones.length &lt;= 30</code></li>
<li><code>1 &lt;= stones[i] &lt;= 1000</code></li>
</ol>
<p><strong>解法一</strong></p>
<p>虽然tag有贪心，但是并不是贪心。。。直接模拟就行了，反而是这题的<a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/last-stone-weight-ii/" >进阶版本<i class="fas fa-external-link-alt"></i></a>，我以为可以这样贪心过，结果发现不对</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lastStoneWeight</span><span class="params">(<span class="keyword">int</span>[] stones)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(stones==<span class="keyword">null</span> ||stones.length&lt;=<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    PriorityQueue&lt;Integer&gt; pq=<span class="keyword">new</span> PriorityQueue&lt;&gt;((a,b)-&gt;b-a);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;stones.length;i++)&#123;</span><br><span class="line">        pq.add(stones[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//NlogN</span></span><br><span class="line">    <span class="keyword">while</span>(pq.size()&gt;<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">int</span> y=pq.poll();</span><br><span class="line">        <span class="keyword">int</span> x=pq.poll();</span><br><span class="line">        pq.add(y-x);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pq.poll();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="920-会议室-LintCode"><a href="#920-会议室-LintCode" class="headerlink" title="920. 会议室(LintCode)"></a><a class="link"   target="_blank" rel="noopener" href="https://www.lintcode.com/problem/meeting-rooms/description" >920. 会议室(LintCode)<i class="fas fa-external-link-alt"></i></a></h2><p>给定一系列的会议时间间隔，包括起始和结束时间[[s1,e1]，[s2,e2]，…(si &lt; ei)，确定一个人是否可以参加所有会议。</p>
<ul>
<li>(0,8),(8,10)在8这这一时刻不冲突</li>
</ul>
<p><strong>样例1</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: intervals = [(<span class="number">0</span>,<span class="number">30</span>),(<span class="number">5</span>,<span class="number">10</span>),(<span class="number">15</span>,<span class="number">20</span>)]</span><br><span class="line">输出: <span class="literal">false</span></span><br><span class="line">解释:</span><br><span class="line">(<span class="number">0</span>,<span class="number">30</span>), (<span class="number">5</span>,<span class="number">10</span>) 和 (<span class="number">0</span>,<span class="number">30</span>),(<span class="number">15</span>,<span class="number">20</span>) 这两对会议会冲突</span><br></pre></td></tr></table></figure>
<p><strong>样例2</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: intervals = [(<span class="number">5</span>,<span class="number">8</span>),(<span class="number">9</span>,<span class="number">15</span>)]</span><br><span class="line">输出: <span class="literal">true</span></span><br><span class="line">解释:</span><br><span class="line">这两个时间段不会冲突</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>这个比较简单，排序后判断相邻的区间是否会覆盖就行了</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="keyword">import</span> <span class="string">&quot;sort&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">canAttendMeetings</span> <span class="params">(intervals []*Interval)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">    <span class="comment">// Write your code here</span></span><br><span class="line">    sort.Slice(intervals, <span class="function"><span class="keyword">func</span><span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">        <span class="keyword">return</span> intervals[i].Start &lt; intervals[j].Start</span><br><span class="line">    &#125;)</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">1</span>; i &lt; <span class="built_in">len</span>(intervals); i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> intervals[i].Start &lt; intervals[i<span class="number">-1</span>].End &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="919-会议室-II-LintCode"><a href="#919-会议室-II-LintCode" class="headerlink" title="919. 会议室 II(LintCode)"></a><a class="link"   target="_blank" rel="noopener" href="https://www.lintcode.com/problem/meeting-rooms-ii/description" >919. 会议室 II(LintCode)<i class="fas fa-external-link-alt"></i></a></h2><p>给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],…] (si &lt; ei)，找到所需的最小的会议室数量。</p>
<p><strong>样例1</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: intervals = [(<span class="number">0</span>,<span class="number">30</span>),(<span class="number">5</span>,<span class="number">10</span>),(<span class="number">15</span>,<span class="number">20</span>)]</span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line">解释:</span><br><span class="line">需要两个会议室</span><br><span class="line">会议室<span class="number">1</span>:(<span class="number">0</span>,<span class="number">30</span>)</span><br><span class="line">会议室<span class="number">2</span>:(<span class="number">5</span>,<span class="number">10</span>),(<span class="number">15</span>,<span class="number">20</span>)</span><br></pre></td></tr></table></figure>

<p><strong>样例2</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: intervals = [(<span class="number">2</span>,<span class="number">7</span>)]</span><br><span class="line">输出: <span class="number">1</span></span><br><span class="line">解释:</span><br><span class="line">只需要<span class="number">1</span>个会议室就够了</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>扫描线的做法，感觉比较简单，也比较好理解（这应该属于最简单的扫描线吧，我看了其他的一些扫描线啥的都是acm里面的内容）<br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200810/nQveo3X6eKxI.png?imageslim"
                      alt="mark"
                ><br>类似就是上图样子，求一个最大的有重合的区间数量，先将起点终点打散后排序，扫描的时候就按照排序后的节点来一个个扫描，然后根据节点的属性来判断是应该+1还是-1，如果是起点就+1，如果遇到终点就-1，整个过程就像是一条线从左往右扫描过去一样</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition of Interval:</span></span><br><span class="line"><span class="comment"> * type Interval struct &#123;</span></span><br><span class="line"><span class="comment"> *     Start, End int</span></span><br><span class="line"><span class="comment"> * &#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * @param intervals: an array of meeting time intervals</span></span><br><span class="line"><span class="comment"> * @return: the minimum number of conference rooms required</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">import</span> <span class="string">&quot;sort&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">type</span> Pair <span class="keyword">struct</span>&#123;</span><br><span class="line">    time <span class="keyword">int</span></span><br><span class="line">    isEnd <span class="keyword">bool</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">minMeetingRooms</span> <span class="params">(intervals []*Interval)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> n = <span class="built_in">len</span>(intervals)</span><br><span class="line">    <span class="keyword">var</span> list []*Pair</span><br><span class="line">    <span class="keyword">var</span> Max = <span class="function"><span class="keyword">func</span> <span class="params">(a,b <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;<span class="keyword">if</span> a&gt;b &#123;<span class="keyword">return</span> a&#125;;<span class="keyword">return</span> b&#125;</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; n; i++ &#123;</span><br><span class="line">        list = <span class="built_in">append</span>(list, &amp;Pair&#123;intervals[i].Start,<span class="literal">false</span>&#125;)</span><br><span class="line">        list = <span class="built_in">append</span>(list, &amp;Pair&#123;intervals[i].End,<span class="literal">true</span>&#125;)</span><br><span class="line">    &#125;</span><br><span class="line">    sort.Slice(list, <span class="function"><span class="keyword">func</span> <span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">        <span class="keyword">return</span> list[i].time &lt; list[j].time</span><br><span class="line">    &#125;)</span><br><span class="line">    <span class="keyword">var</span> res = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> count = <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> _, p := <span class="keyword">range</span> list &#123;</span><br><span class="line">        <span class="keyword">if</span> p.isEnd&#123;</span><br><span class="line">            count--</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            count++</span><br><span class="line">        &#125;</span><br><span class="line">        res = Max(count, res)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>排序+小根堆，按起点排序，然后遍历所有区间，如果某个区间的start大于堆顶的结束时间，说明这两个会议可以公用一个会议室，所以将堆顶弹出，然后将当前会议加入堆中，所以最后堆的大小就是会议室的数量</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//小根堆的思路</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minMeetingRooms</span><span class="params">(List&lt;Interval&gt; intervals)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// Write your code here</span></span><br><span class="line">    Collections.sort(intervals,(i1,i2)-&gt;i1.start-i2.start);</span><br><span class="line">    PriorityQueue&lt;Integer&gt; pq = <span class="keyword">new</span> PriorityQueue&lt;&gt;();</span><br><span class="line">    pq.add(intervals.get(<span class="number">0</span>).end);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; intervals.size(); i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (intervals.get(i).start &gt; pq.peek()) &#123;</span><br><span class="line">            pq.poll();</span><br><span class="line">        &#125;</span><br><span class="line">        pq.add(intervals.get(i).end);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pq.size();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>个人感觉这个思路还是没有上面扫描线简单好理解</p>
<h2 id="391-数飞机-LintCode"><a href="#391-数飞机-LintCode" class="headerlink" title="391. 数飞机(LintCode)"></a><a class="link"   target="_blank" rel="noopener" href="https://www.lintcode.com/problem/number-of-airplanes-in-the-sky/description" >391. 数飞机(LintCode)<i class="fas fa-external-link-alt"></i></a></h2><p>给出飞机的起飞和降落时间的列表，用序列 interval 表示. 请计算出天上同时最多有多少架飞机？</p>
<p><strong>样例 1:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: [(<span class="number">1</span>, <span class="number">10</span>), (<span class="number">2</span>, <span class="number">3</span>), (<span class="number">5</span>, <span class="number">8</span>), (<span class="number">4</span>, <span class="number">7</span>)]</span><br><span class="line">输出: <span class="number">3</span></span><br><span class="line">解释: </span><br><span class="line">第一架飞机在<span class="number">1</span>时刻起飞, <span class="number">10</span>时刻降落.</span><br><span class="line">第二架飞机在<span class="number">2</span>时刻起飞, <span class="number">3</span>时刻降落.</span><br><span class="line">第三架飞机在<span class="number">5</span>时刻起飞, <span class="number">8</span>时刻降落.</span><br><span class="line">第四架飞机在<span class="number">4</span>时刻起飞, <span class="number">7</span>时刻降落.</span><br><span class="line">在<span class="number">5</span>时刻到<span class="number">6</span>时刻之间, 天空中有三架飞机.</span><br></pre></td></tr></table></figure>
<p><strong>样例 2:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: [(<span class="number">1</span>, <span class="number">2</span>), (<span class="number">2</span>, <span class="number">3</span>), (<span class="number">3</span>, <span class="number">4</span>)]</span><br><span class="line">输出: <span class="number">1</span></span><br><span class="line">解释: 降落优先于起飞.</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>和会议室一摸一样，代码稍微改动一点，排序规则需要遵循降落有限</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition of Interval:</span></span><br><span class="line"><span class="comment"> * type Interval struct &#123;</span></span><br><span class="line"><span class="comment"> *     Start, End int</span></span><br><span class="line"><span class="comment"> * &#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * @param airplanes: An interval array</span></span><br><span class="line"><span class="comment"> * @return: Count of airplanes are in the sky.</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">import</span> <span class="string">&quot;sort&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">type</span> Pair <span class="keyword">struct</span> &#123;</span><br><span class="line">    time  <span class="keyword">int</span></span><br><span class="line">    isEnd <span class="keyword">bool</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">countOfAirplanes</span><span class="params">(airplanes []*Interval)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> n = <span class="built_in">len</span>(airplanes)</span><br><span class="line">    <span class="keyword">var</span> list []*Pair</span><br><span class="line">    <span class="keyword">var</span> Max = <span class="function"><span class="keyword">func</span><span class="params">(a, b <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">        <span class="keyword">if</span> a &gt; b &#123;</span><br><span class="line">            <span class="keyword">return</span> a</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> b</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; n; i++ &#123;</span><br><span class="line">        list = <span class="built_in">append</span>(list, &amp;Pair&#123;airplanes[i].Start, <span class="literal">false</span>&#125;)</span><br><span class="line">        list = <span class="built_in">append</span>(list, &amp;Pair&#123;airplanes[i].End, <span class="literal">true</span>&#125;)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//[(1, 2), (2, 3), (3, 4)]</span></span><br><span class="line">    <span class="comment">//随意排序： 1 2start 2end 3start 3end 4 这样最大值就是2，不对</span></span><br><span class="line">    <span class="comment">//所以应该降落优先，将降落时间点的排在前面</span></span><br><span class="line">    sort.Slice(list, <span class="function"><span class="keyword">func</span><span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">        <span class="keyword">if</span> list[i].time == list[j].time &#123;</span><br><span class="line">            <span class="comment">//将end放在前面</span></span><br><span class="line">            <span class="keyword">return</span> list[i].isEnd</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> list[i].time &lt; list[j].time</span><br><span class="line">    &#125;)</span><br><span class="line">    <span class="keyword">var</span> res = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> count = <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> _, p := <span class="keyword">range</span> list &#123;</span><br><span class="line">        <span class="keyword">if</span> p.isEnd &#123;</span><br><span class="line">            count--</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            count++</span><br><span class="line">        &#125;</span><br><span class="line">        res = Max(count, res)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>当然同样可以使用堆，这里就不多写了</p>
<h2 id="NC531-递增数组"><a href="#NC531-递增数组" class="headerlink" title="NC531.递增数组"></a><a class="link"   target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/d0907f3982874b489edde5071c96754a" >NC531.递增数组<i class="fas fa-external-link-alt"></i></a></h2><p>牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？</p>
<ul>
<li>1 &lt;= array.size &lt;= 2*10^5</li>
<li>1 &lt;= array[i] &lt;= 1*10^9</li>
</ul>
<p><strong>示例1</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line">说明: 把第三个数字+<span class="number">2</span>可以构成<span class="number">1</span>，<span class="number">2</span>，<span class="number">3</span></span><br></pre></td></tr></table></figure>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">long</span> <span class="title">IncreasingArray</span> <span class="params">(<span class="keyword">int</span>[] array)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// write code here</span></span><br><span class="line">    <span class="keyword">long</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; array.length; i++)&#123;</span><br><span class="line">        <span class="keyword">if</span> (array[i] &lt;= array[i-<span class="number">1</span>]) &#123;</span><br><span class="line">            res += array[i-<span class="number">1</span>]-array[i]+<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>虽然是easy，还是想了一会儿，我的想法就是当增加一个数的时候就连同<strong>后面的所有数</strong>一起增加，而增加一个数肯定是增加到前一个数+1的次数是最少的（当然我们也不用真的去加，因为后面的区间是整体++，而我们要求的操作次数只是个差值）<br>其实很详细的证明我也给不出来，我只考虑了几种情况</p>
<ol>
<li><code>i</code>后面的部分是单调递增的 3 1(i)  2  3，那么很明显这里和后面一起增加是最优选择</li>
<li><code>i</code>后面是部分是单调递减的 3 3(i)  2  1，那么同样，和后面的一起增加是最优选择，单独选择某一个区间都会导致整体的落差变大，使得后面没增加的部分需要增加的次数增加</li>
<li><code>i</code>后面先递增后递减 3 1(i)  2  1 同上 相当于 递增+递减 看做两部分，（1 2）同增，那么（2，1）也应该随之同增</li>
<li><code>i</code>后面先递减后递增 5 4(i) 3 5  递减+递增 也分成两部分</li>
</ol>
<h2 id="738-单调递增的数字"><a href="#738-单调递增的数字" class="headerlink" title="738. 单调递增的数字"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/monotone-increasing-digits/" >738. 单调递增的数字<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>给定一个非负整数&amp;nbsp;<code>N</code>，找出小于或等于&amp;nbsp;<code>N</code>&amp;nbsp;的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。</p></p>
<p>（当且仅当每个相邻位数上的数字&amp;nbsp;<code>x</code>&amp;nbsp;和&amp;nbsp;<code>y</code>&amp;nbsp;满足&amp;nbsp;<code>x &amp;lt;= y</code>&amp;nbsp;时，我们称这个整数是单调递增的。）</p>

<p>

<p>给定一个非负整数 <code>N</code>，找出小于或等于 <code>N</code> 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。</p>
<p>（当且仅当每个相邻位数上的数字 <code>x</code> 和 <code>y</code> 满足 <code>x &lt;= y</code> 时，我们称这个整数是单调递增的。）</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: N = <span class="number">10</span></span><br><span class="line">输出: <span class="number">9</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: N = <span class="number">1234</span></span><br><span class="line">输出: <span class="number">1234</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: N = <span class="number">332</span></span><br><span class="line">输出: <span class="number">299</span></span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong> <code>N</code> 是在 <code>[0, 10^9]</code> 范围内的一个整数。</p>
<p><strong>示例 1:</strong></p></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: N = <span class="number">10</span></span><br><span class="line">输出: <span class="number">9</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>

<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: N = <span class="number">1234</span></span><br><span class="line">输出: <span class="number">1234</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>

<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: N = <span class="number">332</span></span><br><span class="line">输出: <span class="number">299</span></span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong> N是在<code>[0, 10^9]</code>范围内的一个整数。</p>

<p><strong>解法一</strong></p>
<p>这题写了好几版，总感觉很简单，但是总是有case能把我卡住，最终的思路就是，<strong>逆向遍历</strong>这个数，如果某个数小于前面（左边）的数，那么将前面的数减一，然后记录下当前的下标，最终这个下标后面的数都要变成9</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="comment">//322 -&gt; 299</span></span><br><span class="line"><span class="comment">//243 -&gt; 239</span></span><br><span class="line"><span class="comment">//3524 -&gt; 499</span></span><br><span class="line"><span class="comment">//332 -&gt; 299</span></span><br><span class="line"><span class="comment">//235854 235799</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">monotoneIncreasingDigits</span><span class="params">(N <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> nums []<span class="keyword">int</span></span><br><span class="line">    <span class="comment">//123</span></span><br><span class="line">    <span class="keyword">for</span> N &gt; <span class="number">0</span> &#123;</span><br><span class="line">        nums = <span class="built_in">append</span>(nums, N%<span class="number">10</span>)</span><br><span class="line">        N /= <span class="number">10</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">var</span> res = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> idx = <span class="number">-1</span></span><br><span class="line">    <span class="comment">//213</span></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; <span class="built_in">len</span>(nums)<span class="number">-1</span>; i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> nums[i] &lt; nums[i+<span class="number">1</span>] &#123;</span><br><span class="line">            idx = i</span><br><span class="line">            nums[i+<span class="number">1</span>]--</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> i := <span class="built_in">len</span>(nums) - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i-- &#123;</span><br><span class="line">        <span class="keyword">if</span> i &lt;= idx &#123;</span><br><span class="line">            res = res*<span class="number">10</span> + <span class="number">9</span></span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            res = res*<span class="number">10</span> + nums[i]</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：LeetCode贪心</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2020-01-21 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2020/01/21/a91acf16/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2020/02/02/c517589e/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">并查集</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2019/12/23/d1fa72ec/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">常用的一些工具和网站</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2020/01/21/a91acf16/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#455-%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2"><span class="nav-number">1.</span> <span class="nav-text">455. 分发饼干</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#274-H%E6%8C%87%E6%95%B0"><span class="nav-number">2.</span> <span class="nav-text">274. H指数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#392-%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97"><span class="nav-number">3.</span> <span class="nav-text">392. 判断子序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#621-%E4%BB%BB%E5%8A%A1%E8%B0%83%E5%BA%A6%E5%99%A8"><span class="nav-number">4.</span> <span class="nav-text">621. 任务调度器</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#55-%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F"><span class="nav-number">5.</span> <span class="nav-text">55. 跳跃游戏</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#45-%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F-II"><span class="nav-number">6.</span> <span class="nav-text">45. 跳跃游戏 II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#56-%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4"><span class="nav-number">7.</span> <span class="nav-text">56. 合并区间</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#763-%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4"><span class="nav-number">8.</span> <span class="nav-text">763. 划分字母区间</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#435-%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4"><span class="nav-number">9.</span> <span class="nav-text">435. 无重叠区间</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1288-%E5%88%A0%E9%99%A4%E8%A2%AB%E8%A6%86%E7%9B%96%E5%8C%BA%E9%97%B4"><span class="nav-number">10.</span> <span class="nav-text">1288. 删除被覆盖区间</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#452-%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83"><span class="nav-number">11.</span> <span class="nav-text">452. 用最少数量的箭引爆气球</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1024-%E8%A7%86%E9%A2%91%E6%8B%BC%E6%8E%A5"><span class="nav-number">12.</span> <span class="nav-text">1024. 视频拼接</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#406-%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97"><span class="nav-number">13.</span> <span class="nav-text">406. 根据身高重建队列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1262-%E5%8F%AF%E8%A2%AB%E4%B8%89%E6%95%B4%E9%99%A4%E7%9A%84%E6%9C%80%E5%A4%A7%E5%92%8C"><span class="nav-number">14.</span> <span class="nav-text">1262. 可被三整除的最大和</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5172-%E5%BD%A2%E6%88%90%E4%B8%89%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%8D%E6%95%B0"><span class="nav-number">15.</span> <span class="nav-text">5172. 形成三的最大倍数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1111-%E6%9C%89%E6%95%88%E6%8B%AC%E5%8F%B7%E7%9A%84%E5%B5%8C%E5%A5%97%E6%B7%B1%E5%BA%A6"><span class="nav-number">16.</span> <span class="nav-text">1111. 有效括号的嵌套深度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1353-%E6%9C%80%E5%A4%9A%E5%8F%AF%E4%BB%A5%E5%8F%82%E5%8A%A0%E7%9A%84%E4%BC%9A%E8%AE%AE%E6%95%B0%E7%9B%AE"><span class="nav-number">17.</span> <span class="nav-text">1353. 最多可以参加的会议数目</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#134-%E5%8A%A0%E6%B2%B9%E7%AB%99"><span class="nav-number">18.</span> <span class="nav-text">134. 加油站</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1046-%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8F"><span class="nav-number">19.</span> <span class="nav-text">1046. 最后一块石头的重量</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#920-%E4%BC%9A%E8%AE%AE%E5%AE%A4-LintCode"><span class="nav-number">20.</span> <span class="nav-text">920. 会议室(LintCode)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#919-%E4%BC%9A%E8%AE%AE%E5%AE%A4-II-LintCode"><span class="nav-number">21.</span> <span class="nav-text">919. 会议室 II(LintCode)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#391-%E6%95%B0%E9%A3%9E%E6%9C%BA-LintCode"><span class="nav-number">22.</span> <span class="nav-text">391. 数飞机(LintCode)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#NC531-%E9%80%92%E5%A2%9E%E6%95%B0%E7%BB%84"><span class="nav-number">23.</span> <span class="nav-text">NC531.递增数组</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#738-%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97"><span class="nav-number">24.</span> <span class="nav-text">738. 单调递增的数字</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
